package demo1;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Test {
    public int lengthOfLongestSubstring(String s) {
        int sz = s.length();
        int len = 0;
        int left = 0;
        HashSet<Character> set = new HashSet<>();
        for (int right = 0; right < sz; ) {
            char ch = s.charAt(right);
            if(!set.contains(ch)){
                set.add(ch);
                right++;
            }else {
                //len = Math.max(len,right-left);
                while (left <= right && s.charAt(left) != ch) {
                    set.remove(s.charAt(left));
                    left++;
                }
                left++;
                right++;
            }
            len = Math.max(len,right-left);
        }
        return len;
    }

    public int maxHeightOfTriangle(int red, int blue) {
        int redHight = 0;
        int blueHight = 0;
        int sum = 1;
        while (red > 0 && blue > 0) {
            red -= sum++;
            redHight++;
            if (blue >= sum) {
                blue -= sum++;
                redHight++;
            }else {
                break;
            }
        }
        sum = 1;
        while (red > 0 && blue > 0) {
            blue -= sum++;
            blueHight++;
            if (red >= sum) {
                red -= sum++;
                blueHight++;
            }else {
                break;
            }
        }
        return Math.max(redHight,blueHight);
    }

    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                len = Math.min(len,right-left+1);
                sum -= nums[left++];
            }
        }
        return len;
    }


    public static void main1(String[] args) {
        int[] array = {1000000000,1000000000,1000000000,1000000000};
        fourSum(array,-294967296);
        int sz = array.length;
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int sz = nums.length;
        List<List<Integer>> list = new LinkedList<>();
        for (int i = 0; i <= sz-4; i++) {
            if(i!=0 && nums[i] - nums[i-1]==0){
                continue;
            }
            Long t = (long)target - nums[i];
            for (int j = i+1; j <= sz-3; j++) {
                if(j!=i+1 && nums[j] - nums[j-1]==0){
                    continue;
                }
                Long tt = (long)(t-nums[j]);
                int l = j+1;
                int r = sz-1;
                while (l < r) {
                    if(l!=j+1 && nums[l]-nums[l-1]==0){
                        l++;
                        continue;
                    }
                    if(r!=sz-1 && nums[r] - nums[r+1]==0){
                        r--;
                        continue;
                    }
                    if (tt.compareTo((long)nums[l]+nums[r])==0) {
                        List<Integer> list1 = new LinkedList<>();
                        list1.add(nums[i]);
                        list1.add(nums[j]);
                        list1.add(nums[l]);
                        list1.add(nums[r]);
                        list.add(list1);
                        l++;
                        r--;
                        continue;
                    } else if (tt.compareTo((long)nums[l]+nums[r])>0) {
                        l++;
                        continue;
                    }else {
                        r--;
                        continue;
                    }
                }
            }
        }
        return list;
    }
}
